package FloodFill;

import java.util.LinkedList;
import java.util.Queue;

public class MaxAreaOfIsland {
    // 辅助向量数组
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,-1,1};

    // 辅助布尔访问数组
    boolean[][] visit;

    int m; // 对应 x 坐标
    int n; // 对应 y 坐标

    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        visit = new boolean[m][n];

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && visit[i][j] == false) {
                    maxArea = Math.max(maxArea, bfs(grid, i, j));
                }
            }
        }

        return maxArea;
    }

    public int bfs(int[][] grid, int OOx, int OOy) {
        // 记录岛屿的面积
        int size = 0;

        // 用队列保存该原点
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{OOx, OOy});
        // 该点已访问
        visit[OOx][OOy] = true;
        // 岛屿面积 + 1
        size++;

        // bfs
        while(!queue.isEmpty()) {
            // 取出点
            int[] point = queue.poll();
            // 分解点
            int Ox = point[0];
            int Oy = point[1];

            // 遍历下一层节点, offer岛屿
            for(int i = 0; i < 4; i++) {
                int x = Ox + dx[i];
                int y = Oy + dy[i];

                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && visit[x][y] == false) {
                    queue.offer(new int[]{x, y});
                    visit[x][y] = true;
                    size++;
                }
            }
        }

        return size;
    }
}
